package com.leetcode.practice.leetcode;

/**
 * 给你一棵二叉搜索树，请你 按中序遍历 将其重新排列为一棵递增顺序搜索树，使树中最左边的节点成为树的根节点，并且每个节点没有左子节点，只有一个右子节点。
 */
public class No897 {

    static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;
        TreeNode() {}
        TreeNode(int val) { this.val = val; }
        TreeNode(int val, TreeNode left, TreeNode right) {
          this.val = val;
          this.left = left;
          this.right = right;
        }
    }

    /**
     * 构建搜索二叉树
     * 规则:比节点小的在左子树，大的在右子树
     *
     * @param nums
     * @return
     */
    private void initTreeNode(Integer num, TreeNode root){
        if(num == null){
            return;
        }

        if(num >= root.val){
            if(root.right == null){
                root.right = new TreeNode(num);
            }else{
                initTreeNode(num,root.right);
            }
        }else{
            if(root.left == null){
                root.left = new TreeNode(num);
            }else{
                initTreeNode(num,root.left);
            }
        }
    }

    public static void main(String[] args) {
        No897 no897 = new No897();
        Integer[] nums = {5,3,6,2,4,null,8,1,null,null,null,7,9};
        TreeNode treeNode = new TreeNode(Integer.MIN_VALUE);
        for (int i = 0; i < nums.length; i++) {
            if(i == 0){
                treeNode.val = nums[i];
            }else{
                no897.initTreeNode(nums[i],treeNode);
            }
        }
        no897.increasingBST(treeNode);
    }


    /**
     * 2.节点移动法
     * 将节点挂在新的树下，利用搜索二叉树特性，遍历过的左节点不再遍历的特性，修改原tree挂在新的tree下边
     * @param root
     * @return
     */
    private TreeNode currentNode;//记录当前节点

    public TreeNode increasingBST(TreeNode root) {
        TreeNode head = new TreeNode(Integer.MIN_VALUE);
        currentNode = head;
        createNode(root);
        return head.right;
    }

    private void createNode(TreeNode root) {
        if(root == null){
            return;
        }

        createNode(root.left);
        currentNode.right = root;
        root.left = null;
        currentNode = currentNode.right;
        createNode(root.right);
    }


/*
    1.暴力构建法
    遍历时根据搜索二叉树左小右大原则，将值填入集合中，将成为排好序的列表
    将排序后的列表重新构建一个只有右节点的树

    public TreeNode increasingBST(TreeNode root) {
        List<Integer> list = new ArrayList<>();
        createList(root,list);
        TreeNode head = new TreeNode(list.get(0));
        TreeNode current = head;
        for (int i = 1; i < list.size(); i++) {
            current.right = new TreeNode(list.get(i));
            current = current.right;
        }
        return head;
    }

    private void createList(TreeNode root, List<Integer> list){
        if(root == null){
            return;
        }
        createList(root.left,list);
        list.add(root.val);
        createList(root.right,list);
    }
*/

}
